#include <catch2/catch.hpp>

#include "solution.hpp"

using namespace solution_023;

namespace
{

template<int remains, typename arg, typename... args>
struct append
{
    static ListNode* impl(arg val, args... vals) {
        ListNode* l = new ListNode(val);
        l->next = append<sizeof...(args)-1, args...>::impl(vals...);
        return l;
    }
};

template<typename arg>
struct append<0, arg> {
    static ListNode* impl(arg val) {
        return new ListNode(val);
    }
};

template<typename... args>
ListNode* make_list(args... vals)
{
    return append<sizeof...(args)-1, args...>::impl(vals...);
}

std::vector<int> convert(const ListNode* list)
{
    std::vector<int> ilist;
    while (list) {
        ilist.push_back(list->val);
        list = list->next;
    }
    return ilist;
}

void destroy_list(ListNode* head)
{
    while (head) {
        auto node = head;
        head = head->next;
        delete node;
    }
}

}

TEST_CASE("23. Merge k Sorted Lists", "[023]") {

SECTION("example 1") {
    std::vector lists {make_list(1,4,5),make_list(1,3,4),make_list(2,6)};
    auto lists_backup = lists;
    auto ans = Solution().mergeKLists(lists);
    CHECK(convert(ans) == std::vector{1,1,2,3,4,4,5,6});
    for (auto head : lists_backup)
        destroy_list(head);
    destroy_list(ans);
}

SECTION("example 2") {
    std::vector<ListNode*> lists;
    CHECK(convert(Solution().mergeKLists(lists)).empty());
}

SECTION("example 3") {
    std::vector<ListNode*> lists {nullptr};
    CHECK(convert(Solution().mergeKLists(lists)).empty());
}

SECTION("example 4") {
    std::vector<ListNode*> lists {nullptr, nullptr};
    CHECK(convert(Solution().mergeKLists(lists)).empty());
}

}
